package leetcode.code673;

import java.util.Arrays;
import java.util.Stack;

/**
 * 内存超了
 *
 * @author CaoYu
 * @date 2021年9月18日
 * @description
 */
public class Solution extends Solution673 {

	@Override
	public int findNumberOfLIS(int[] nums) {
		// [1,3,5,4,7]
		// [1,3,5,4,1,2,3,7] 只有更新最后一位的算
		// [3,1,2] 1
		// 1,5,4,2,3
		// 1,5,4,2,6
		// 1,5,4,2,1,3
		// 1,5,4,2,1,6
		// [1,2,4,3,5,4,7,2]
		// 1,2,3,1,2,3,4
		int max = 0;
		int min = Integer.MAX_VALUE;// 有负数
		for (int num : nums) {
			max = Math.max(max, num);
			min = Math.min(min, num);
		}
		int index = 0;
		if (min < 0) {
			index = -min;
		}
		Stack<Integer> s1 = new Stack<>();
		Stack<Integer> s2 = new Stack<>();
		s1.add(nums[0]);
		int[][] numsoflen = new int[nums.length + 1][max + 1 + index];// [长度][以数字结尾]得个数
		Arrays.fill(numsoflen[0], 0);
		numsoflen[1][nums[0] + index] = 1;
		for (int i = 1; i < nums.length; i++) {
			if (s1.peek() < nums[i]) {
				s1.add(nums[i]);
				int total = 0;
				for (int j = 0; j < nums[i] + index; j++) {
					total += numsoflen[s1.size() - 1][j];
				}
				numsoflen[s1.size()][nums[i] + index] = total == 0 ? 1 : total;// [1,2,4,3,5,4,7,2]
			} else if (s1.peek() > nums[i]) {
				while (!s1.isEmpty() && s1.peek() >= nums[i]) {
					s2.add(s1.pop());
				}
				s2.pop();
				s1.add(nums[i]);
				int total = 0;
				for (int j = 0; j < nums[i] + index; j++) {
					total += numsoflen[s1.size() - 1][j];
				}
				numsoflen[s1.size()][nums[i] + index] += total == 0 ? 1 : total;
				while (!s2.isEmpty()) {
					s1.add(s2.pop());
				}
			} else if (s1.peek() == nums[i]) {
				int total = 0;
				for (int j = 0; j < nums[i] + index; j++) {
					total += numsoflen[s1.size() - 1][j];
				}
				numsoflen[s1.size()][nums[i] + index] += total == 0 ? 1 : total;
			}
		}
		int total = 0;
		for (int i = 0; i <= max + index; i++) {
			total += numsoflen[s1.size()][i];
		}
		return total;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
	}

}
